1. Field of the Invention
The invention relates to a method of controlling the transmission of data between a plurality of identified stations interconnected via a communication channel comprising at least an upstream channel at least partially shared by said stations, said upstream channel being divided into successive time slots of predetermined length consisting of a data slot and m control minislots, said method comprising:
(A) a reservation step, provided for defining a transmission order, within said control minislots, of data packet transmission requests generated by the stations and a transmission order of the corresponding data packets within the data slots; PA1 (B) a transmission step, according to the following sub-steps: PA1 (a) the channel time is now divided into another type of time slot each of which consists of a constant number m of minislots (said control minislots) and one data slot; PA1 (b) each station (or user) participates in the constitution of two common queues: PA1 (C) a congestion resolution step, consisting of a conversion sub-step of at least an idle data slot into p additional control minislots as soon as and so longer as the number of requests is greater than a predetermined threshold. PA1 (C) a congestion resolution step, consisting of a conversion sub-step provided for increasing by p additional control minislots the predetermined length of the time slots as soon as and so long as the number of requests is greater than a predetermined threshold. PA1 (A) a local transmission request queue for a reserved transmission, within said control minislots and according to a defined transmission order, of transmission requests corresponding to data packets generated by the station; PA1 (B) a local packet transmission queue for a reserved transmission, within said data slots and according to the transmission order of acknowledgement signals received in reply to said transmission requests, of the data packets corresponding to these requests; PA1 (C) access control means of the transmission requests and the data packets to the upstream channel; PA1 (A) a transmission request queue for a reserved transmission, within said control minislots and according to a defined transmission order, of transmission requests corresponding to data packets generated by said stations; PA1 (B) a packet transmission queue for a reserved transmission, within said data slots and according to the transmission order of acknowledgement signals received in reply to said transmission requests, of the data packets corresponding to these requests; PA1 (C) access control means of the transmission requests and the data packets to the upstream channel;
(a) transmission of the data packet transmission requests via the upstream channel, in response to generated data packets; PA2 (b) transmission of the data packets via the upstream channel; PA2 (1) the first one, called data transmission queue, organizes an ordered transmission of data packets emitted by stations within the data slots; PA2 (2) the second one, called collision resolution queue, is activated when immediate access of a message to the channel is not possible, due to collisions between several data packets emitted simultaneously, and allows (also thanks to an ordered transmission of transmission requests) to resolve these collisions or to prevent further ones to occur.
The invention also relates to head-end and communication stations for carrying out this method, and to communication systems including such head-end stations.
This invention may be appreciated for satellite communication networks or any further kind of connection between remote stations, computers, and so on, and can be particularly used in the field of interactive television. More generally, the invention is useful in any situation in which various types of data processing devices have to communicate between them.
2. Description of the Prior Art
When such data processing devices, called stations for example, are interconnected through a common communication medium to form a network, they communicate according to a data communication protocol, that defines a set of rules organized in an accurate fashion. Generally speaking, the protocols can be classified as being either conflict-free or collision type. It is clear for instance that no problem of communication occurs when only two stations have to transmit data to each other. When more than two stations must communicate with one another over a common channel, it is likely (since all users can initiate transmission at arbitrary instants) that two users or more will decide to emit messages simultaneously, which leads to a collision between these messages (the concerned stations are said in contention). The data communication protocol must then be sophisticated enough to manage the loss of network throughput due to such collisions.
It has then be proposed a first family of protocols, according to which the channel time is divided into equally sized transmission slots and the messages into fixed length packets. These time slots may be known by their position within frames of fixed length and specifically assigned to each user who will therefore always send his message (comprising one or several fixed length packets) in the same time slots, for instance the i-th of each frame. The addressee simply knows that he has to listen to said i-th time slot of each frame in order to receive the message. Such a protocol is however limited to constant bitrate applications.
In a second family of protocols, the stations always generate messages of fixed length for transmission within slots of appropriate fixed length, but these time slots are no longer dedicated to specific users. One of the stations or a predetermined head-end station takes generally the control of the channel and of the traffic. When an user sends in any of the time slots a message regardless of what other users are doing, the head-end sends to said user an acknowledgement signal only if the message is well received. When no indication is returned, it means that a wrong transmission occurred (generally a collision between two or more messages, damaging all messages transmitted), and the user resends his message, until he receives the waited acknowledgement signal indicating that the transmission is now successful. In case of high loads, such re-transmissions may however require too much time.
An improved protocol, providing immediate access to the channel at light loads and better performances as the channel load grows, is described in the U.S. Pat. No. 5,390,181. According to this protocol, called DQRAP in a shorter form (Distributed Queueing Random Access Protocol), two conditions are fulfilled:
This protocol DQRAP works in the following way. When a station wants to transmit a message (in a data slot), it must first transmit a corresponding message request in one of the control minislots, selected by rolling a m-sided die, m being generally rather weak and for instance equal to 3. If no other station is sending a similar transmission request at the same moment, the request can start immediately in the selected minislot and arrives safely at the head-end station which accepts it and broadcasts a corresponding acknowledgement signal to the stations. The message can then either be transmitted immediately if the data transmission queue is empty or take the following free place in said queue if some messages are already waiting for their transmission. On the contrary, when two or more stations try to send a message request in the same minislot simultaneously, collisions occur and none of the requests can be transmitted, which leads each user to try to ask for a re-transmission of his request (by rolling once more the m-sided die and selecting another minislot in the following set of minislots). This action must be performed until the conflict is solved, with a resulting loss of network efficiency.
Moreover, when the number of message transmission requests becomes very high, the number of collisions also increases and more and more minislots are required to solve them (at least two more minislots for each collision). As the number of available minislots is limited to m per time slot, an increasing time is required in order to consider the collisions and to answer new requests.